package com.captain.special.二叉树.简单;

import com.captain.leetcode.TreeNode;

import java.util.*;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/9 11:50
 */
public class 二叉树的堂兄弟节点993 {
    int l;
    int r;
    List<Integer> ans;
    Map<TreeNode, TreeNode> map = new HashMap<>();
    Map<TreeNode, Integer> mapDepth = new HashMap<>();

    public boolean isCousins(TreeNode root, int x, int y) {
        l = x;
        r = y;
        ans = new ArrayList<>();
        recur(root, null);
        if (map.size() != 2) {
            return false;
        }
        TreeNode n1 = null;
        TreeNode n2 = null;
        Set<TreeNode> treeNodes = map.keySet();
        for (TreeNode treeNode : treeNodes) {
            if (n1 == null) {
                n1 = treeNode;
            }
            n2 = treeNode;
        }
        for (TreeNode key : treeNodes) {
            TreeNode parent = map.get(key);
            if (parent == null || parent.equals(root)) {
                return false;
            }
            //对n2进行比较
            if (key.equals(n1)) {
                if (parent.equals(n2)) {
                    return false;
                }
            } else {
                if (parent.equals(n1)) {
                    return false;
                }
            }
        }
        return !map.get(n1).equals(map.get(n2)) && mapDepth.get(n1).equals(mapDepth.get(n2));
}

    public void recur(TreeNode node, TreeNode parent) {
        if (node == null) {
            return;
        }
        if (ans.size() == 2) {
            return;
        }
        recur(node.left, node);
        int val = node.val;
        if (val == l || val == r) {
            map.put(node, parent);
            mapDepth.put(node, depth(node));
        }
        recur(node.right, node);

    }

    public int depth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = depth(node.left);
        int right = depth(node.right);
        return Math.max(left, right) + 1;
    }
}
